Weird. I can't offer any words of advice to be honest. The only thing I can think of is that a NotesDocumentCollection derived from an FTSearch is ordered, whereas a NotesDatabase.Search-derived one is not... but I don't see how that would have an effect. Do let us know if you get anywhere with this!
--
http://www.benpoole.com